Another specialization of recognizable picture languages are the deterministic
ones. To define this kind of picture languages we use tiling systems again.
Like UREC deterministic REC can be categorized. First, we will present the
$c2c$-determinstic tiling systems where $c2c \in \{tl2br, tr2bl, bl2tr,
br2tl\}$. These tiling systems were introduced in 2007 by M. Anselmo, D.
Giammarresi and M. Madonia in~\cite{anselmo2007recognizable}. The main idea
is based on the OTA presented in Section~\ref{ota}. This kind of deterministic
tiling system scans a picture $p \in \Sigma^{*,*}$ from one corner to the
diagonal one. While scanning $p$ the system builds the local picture $p' \in
LOC(\Theta) \subseteq \Gamma^{*,*}$. Important is that every position $(x, y)
\in P(l_1(p), l_2(p))$ can only be read if for the $tl2br$-deterministic tiling
system for example all the positions above and left from $(x, y)$ were
already read. Formally, it is the following:
\begin{definition}
A tiling system $(\Sigma, \Gamma, \Theta, \pi)$ is \emph{tl2br-deterministic} if
for any $\gamma_1, \gamma_2, \gamma_3 \in \Gamma \cup \{\#\}$ and
$\sigma \in \Sigma$ there exists at most one tile $t \in \Theta$ with \(t =
\begin{smallmatrix} 
 \gamma_1 & \gamma_2 \\
 \gamma_3 & \gamma_4
\end{smallmatrix}
\), and $\pi(\gamma_4) = \sigma$.
\end{definition}
$L \in REC$ is a diagonal deterministic picture language iff it can be
recognized by a $c2c$-deterministic tiling system for some $c2c$. We denote the
family of all diagonal deterministic recognizable picture languages as
$Diag$-DREC. M. Anselmo, D. Giammarresi and M. Madonia have denoted this class
of picture languages by DREC in~\cite{anselmo2007recognizable}. Later V. Lonati
and M.
Pradella called this family $Diag$-DREC in~\cite{lonati2009snakedeterministic}.

As an example for a tiling system that is $tl2br$-deterministic we can cite the
language $L_{fr = fc}$ of Section~\ref{urec} and the tiling system of
Example~\ref{unambiguousTilingSystemExample}. Remark that this tiling system is
not $br2tl$-deterministic. The reasons are the next two tiles of the set of
tiles $\Theta$ of the tiling system:
\begin{center}
\begin{tabular}{|D{0.38cm}|D{0.38cm}|}
\hline
 $a_{a}^1$ & $a_{a}^2$ \tabularnewline
\hline
 $a_{a}^0$ & $b_{a}^1$ \tabularnewline
\hline
\end{tabular}, 
\begin{tabular}{|D{0.38cm}|D{0.38cm}|}
\hline
 $a_{b}^1$ & $a_{a}^2$ \tabularnewline
\hline
 $a_{a}^0$ & $b_{a}^1$ \tabularnewline
\hline
\end{tabular} $\in \Theta$ with $\pi(a_{a}^1) = \pi(a_{b}^1) = a$.
\end{center} 
Another idea of deterministic tiling systems, introduced 2009
in~\cite{lonati2009snakedeterministic} by V. Lonati and M. Pradella, is to
read a picture $p \in \Sigma^{*,*}$ by scanning $p$ with a polite scanning
strategy (see~\cite{lonati2010picture} and~\cite{lonati2011strategies}).
The following definitions of polite scanning strategies are
from~\cite{lonati2010picture}.
\begin{definition}
A scanning strategy is a family $\mu = \{\mu_{n \times m} : \{1, 2, \ldots\}
\rightarrow n \times m\}_{n, m}$ and $\mu_{n \times m}$ is called the scanning
function over domain $n \times m$.
\end{definition}
$\mu$ is \emph{continuous} if $\mu_{n \times m}(i + 1)$ is
adjacent to $\mu_{n \times m}(i)$ for every n, m, i and is \emph{one-pass} if
each scanning function $\mu_{n \times m}$ restricted to $\{1, 2, \ldots, nm\}$ is a
bijection. 

To explain a polite scanning strategy we need the definition of a
next-position function. Therefore we need some notations.

For a position $y$ in a picture $p$, $edges(y)$ describes the 4 edges
adjacent to $y$. An edge is a pair of adjacent positions. We call $Dirs = \{r,
l, t, b\}$ the set of directions.
$y \mid d$ denotes the edge at position $y$ in direction $d \in Dirs$, and $y
\plusinbox d$ denotes the position adjacent to $y$ in direction $d$.
\begin{definition}
A next position function is a partial function $\eta : 2^{Dirs} \times Dirs
\rightarrow Dirs$ such that  $\eta(D, d) = \perp$ if $d \not\in D$.
\end{definition}
Informally, a next position function is used to choose where to go next. This
decision can be made by using the set of already considered edges and the
currently considered one.

Next we want to define the scanning function $\mu_{n \times m}$ over $n \times
m$ by using a fixed next-position function $\eta$, a starting corner $c_s \in
Corners = \{$tl$, $tr$, $br$, $bl$\}$ and a starting direction $d_s \in Dirs$.
\begin{compactitem}
\item The starting position is
\begin{align*}
\mu_{n \times m}(1) = \left\{\begin{array}{ll}
								(1, 1) & \text{ if } c_s = \text{ tl } \\
								(1, m) & \text{ if } c_s = \text{ tr } \\
								(n, 1) & \text{ if } c_s = \text{ bl } \\
								(n, m) & \text{ if } c_s = \text{ br }
							\end{array}
					  \right.
\end{align*}
Let $E_1$ be the set of edges which are adjacent to border positions of the
picture domain $n \times m$, and $d_1 = d_s$.
\item The inductive definition of $\mu_{n \times m}(i + 1)$, $d_{i + 1}$,
$D_{i}$ and $E_{i + 1}$ for $i \geq 1$ is given by
\begin{align*} 
\begin{array}{ll}
D_{i} = \{d \in Dirs : \mu_{n \times m}(i) \mid d \in E_i\} 
		& E_{i + 1} = E_i \cup edges(\mu_{n \times m}(i)) \\
d_{i + 1} = \eta(D_i, d_i) 
		& \mu_{n \times m}(i + 1) = \mu_{n \times m}(i) \plusinbox d_{i + 1}
\end{array}
\end{align*}
To define $\eta(D_1, d_1)$, $\mu_{n \times m}(1) \mid d_1$ must be in $E_1$.
\end{compactitem}

A scanning strategy $\mu$ is induced by a triple $\langle\eta, c_s,
d_s\rangle$ if $\mu = \{\mu_{n \times m}\}_{n \times m}$. Furthermore, a
scanning strategy can be called blind, if it neither ``sees'' the picture
content, nor its size. A blind scanning strategy can only ``feel'' a border or
already visited positions. Formally, it is the following:
\begin{definition}
A scanning strategy is \emph{blind} if it is induced by a triple $\langle\eta,
c_s, d_s\rangle$, where $\eta$ is a next position function, $c_s$ a starting corner,
and $d_s$ a starting direction.
\end{definition}
Now we can explain what a polite scanning strategy is.
\begin{definition}
A scanning strategy is called \emph{polite} if it is blind and one-pass.
\end{definition}
In \cite{lonati2011strategies} it was proved that any polite scanning strategy
has to follow, except for some bootstrap steps, one of four kinds of movements,
or their rotations and symmetrical, intuitively exemplified by the following
pictures.
\begin{center}
\footnotesize
\begin{minipage}[b]{0.2\linewidth}
\begin{center}
\begin{tabular}{|D{0.34cm}|D{0.34cm}|D{0.34cm}|D{0.34cm}|}
\hline
 1 & 6 & 7 & 12 \tabularnewline
\hline
 2 & 5 & 8 & 11 \tabularnewline
\hline
 3 & 4 & 9 & 10 \tabularnewline
\hline
\end{tabular}
\captionof{table}{(a) snake($\mathcal{S}$)}
\end{center}
\end{minipage}
\hfill
\begin{minipage}[b]{0.2\linewidth}
\begin{center}
\begin{tabular}{|D{0.34cm}|D{0.34cm}|D{0.34cm}|D{0.34cm}|}
\hline
 1 & 10 & 11 & 12 \tabularnewline
\hline
 2 & 9  & 8  & 7  \tabularnewline
\hline
 3 & 4  & 5  & 6  \tabularnewline
\hline
\end{tabular}
\captionof{table}{(b) L-like($\mathcal{L}$)}
\end{center}
\end{minipage}
\hfill
\begin{minipage}[b]{0.2\linewidth}
\begin{center}
\begin{tabular}{|D{0.34cm}|D{0.34cm}|D{0.34cm}|D{0.34cm}|}
\hline
 1 & 12 & 9  & 8 \tabularnewline
\hline
 2 & 11 & 10 & 7 \tabularnewline
\hline
 3 & 4  & 5  & 6 \tabularnewline
\hline
\end{tabular}
\captionof{table}{(c) U-like($\mathcal{U}$)}
\end{center}
\end{minipage}
\hfill
\begin{minipage}[b]{0.2\linewidth}
\begin{center}
\begin{tabular}{|D{0.34cm}|D{0.34cm}|D{0.34cm}|D{0.34cm}|}
\hline
 1 & 10 & 9  & 8 \tabularnewline
\hline
 2 & 11 & 12 & 7 \tabularnewline
\hline
 3 & 4  & 5  & 6 \tabularnewline
\hline
\end{tabular}
\captionof{table}{(d) spiral($\mathcal{C}$)}
\end{center}
\end{minipage}
\normalsize
\end{center}
The directions of the here depicted versions are called left-to-right. In the
case of the snake-like strategy we denoted it by $\mathcal{S}^{l2r}$, while its
rotation is denoted by $\mathcal{S}^{t2b}$. The closure under rotation and
mirrowing of one strategy, for example the snake-like one, is denoted by
$\mathcal{S}$.

After we know what a scanning strategy is we can show another deterministic
tiling system. The deterministic tiling system that uses a polite scanning
strategy is called $\mu$-deterministic tiling system, abbreviated as
$\mu$-DTS, where $\mu$ is a polite scanning strategy. The first definition can
be found in~\cite{lonati2009snakedeterministic}, further work are
in~\cite{lonati2010picture},~\cite{lonati2011towards}
and~\cite{lonati2011strategies}.
\begin{definition}
A tiling system $(\Sigma, \Gamma, \Theta, \pi)$ is
$\mathcal{S}^{t2b}$-deterministic if $\Gamma$ and $\Theta$ can be partioned as
$\Gamma = \Gamma_1 \cup \Gamma_2$, $\Theta = \Theta_1 \cup \Theta_2$, where 
\begin{compactitem}
  \item $(\Sigma, \Gamma, \Theta_1, \pi)$ is $tl2br$-deterministic and for each
  tile $t \in \Theta_1, t(i, j) \in \Gamma_{3-i} \cup \{\#\}$
  \item $(\Sigma, \Gamma, \Theta_2,\pi)$ is $tr2bl$-deterministic and for each
  tile $t \in \Theta_2, t(i, j) \in \Gamma_{i} \cup \{\#\}$ and not both
  $t(1,1), t(1,2)$ are $\#$.
\end{compactitem}
\end{definition}
The family of all $\mu$-DTS is called $\familyOf{$\mu$-DTS}$. V. Lonati and M.
Pradella called $\mathcal{S}^{t2b}$-DTS in~\cite{lonati2009snakedeterministic}
$Snake$-DTS and the closure under rotation of $\familyOf{$Snake$-DTS}$
$Snake$-DREC.

After all this information about determinstic tiling systems we want to present
some closure properties. The next theorem was proved
in~\cite{anselmo2007recognizable}.
\begin{theorem}
The family $Diag$-DREC is closed under complement and rotation but it is not
closed under intersection.
\end{theorem}
The following theorem was proved
in~\cite{lonati2009snakedeterministic}.
\begin{theorem}
$Snake$-DREC is closed under complement, rotation and mirrors, but not under
intersection.
\end{theorem}
At last in this chapter we want to talk about the family dependencies.
\begin{theorem}
$Diag$-DREC $\subset$ $Col$-UREC $\cap$ $Row$-UREC. 
\end{theorem}
\begin{proof}
This theorem is proved by~\cite{anselmo2007recognizable} through the using the
picture language $L_{frames}$. 
\begin{align*}
L_{frames} = \{p \in \Sigma^{*,*} \mid& l_1(p) =
l_2(p) = n, p(n, i) = p(i, n), p(2, i) = p(n - i + 1, n - 1),\\
&p(i, 1) = p(1, i) \text{ and } p(n -1, i) = p(n - i + 1, 2) \\
&\text{for all } i \in \{1, \ldots, n\}\}
\end{align*}
is the language of all square pictures, where the first row is equal to the first
column, the last row equals the last column, the second row is equal to the
reverse of the second-last column and the second-last row is equal to the
reverse of the second column. It was proved that $L_{frames} \in$ $Col$-UREC
$\cap$ $Row$-UREC and $L_{frames} \not\in$ $Diag$-DREC.
\end{proof}
Also in~\cite{anselmo2007recognizable} the following theorem is proved.
\begin{theorem}
The class $Diag$-DREC is equal to the closure by rotation of $\familyOf{DOTA}$. 
\end{theorem}
\begin{theorem}
$Snake$-DREC = $Col$-UREC $\cup$ $Row$-UREC.
\end{theorem}
This follows by $\familyOf{$snake$-DTS} = \familyOf{$t2b$-UTS}$, by applying
rotation. See~\cite{lonati2009snakedeterministic} for the proof of
$\familyOf{$snake$-DTS} = \familyOf{$t2b$-UTS}$.

In~\cite{prusa2012new} and~\cite{prusa2012sgraffito} the following theorem was
proved.
\begin{theorem}
$Diag$-DREC $\subseteq \familyOf{2DSA}$.
\end{theorem}
In the proof a 2DOTA is simulated by a 2DSA, so $\familyOf{2DOTA} \subseteq
\familyOf{2DSA}$. Because $\familyOf{2DSA}$ is closed under rotation and the
closure of rotation of $\familyOf{2DOTA}$ is equal to $Diag$-DREC the theorem
follows.
\label{drec}